package com.mzy.linear_struct.ks;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: mizy3
 * @Date: 2024/09/04/下午9:54
 * @Description:
 */
public class Pro74合并区间 {

    /*
    public int[][] merge(int[][] intervals) {
        // 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
        // 输出：[[1,6],[8,10],[15,18]]
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // [1...3]
            //    [2.....6]
            //              [8...10]
            //                       [15...18]
            // 如果当前的左边界 <= 上一个的右边界，则证明可以合并区间
            if (intervals[i][0] <= ans.get(ans.size() - 1)[1]) {
                int[] ints = ans.get(ans.size() - 1);
                // 这里取最大值是防止出现这种情况
                // [1.......4] a
                //   [2...3] b

                // 如果直接让 a[1] = b[1]，结果就有问题
                ints[1] = Math.max(intervals[i][1], ints[1]);
            } else {
                ans.add(intervals[i]);
            }

        }
        return ans.toArray(new int[ans.size()][]);
    }
    */

    public static void main(String[] args) {
        int[][] input = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] ans = new Pro74合并区间().merge(input);
        System.out.println(Arrays.toString(ans));

    }

    private int[][] merge(int[][] intervals) {
        // 1...3
        //   2....6
        //          8...10
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        ArrayList<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= ans.get(ans.size() - 1)[1]) {
                int[] ints = ans.get(ans.size() - 1);
                ints[1] = Math.max(intervals[i][1], ints[1]);
            } else {
                ans.add(intervals[i]);
            }
        }


        return ans.toArray(new int[ans.size()][]);
    }

    /*
    private int[][] merge(int[][] intervals) {

        // 1...3
        //   2....6
        //           8...10
        //                  15...18
        ArrayList<int[]> ans = new ArrayList<>();

        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] <= ans.get(ans.size() - 1)[1]){
                int[] ints = ans.get(ans.size() - 1);
                ints[1] = Math.max(intervals[i][1], ints[1]);
            }else {
                ans.add(intervals[i]);
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }
    */

    /*private int[][] merge(int[][] intervals) {
        // 1...3
        //   2....6
        //          8...10
        //                 15...18

        ArrayList<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= ans.get(ans.size() - 1)[1]) {
                ans.get(ans.size() - 1)[1] = Math.max(intervals[i][1], ans.get(ans.size() - 1)[1]);
            } else {
                ans.add(intervals[i]);
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }*/

    /*private int[][] merge(int[][] intervals) {

        List<int[]> ans = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // 1..3
            //  2....6
            //         8...10
            //                15...18
            if (intervals[i][0] <= ans.get(ans.size() - 1)[1]) {
                int[] section = ans.get(ans.size() - 1);
                section[1] = Math.max(section[1], intervals[i][1]);
            } else {
                ans.add(intervals[i]);
            }

        }
        return ans.toArray(new int[ans.size()][]);
    }*/
}
